package com.tgy.algorithm.base._并查集;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class UFNode01<V> {
    V value;
    UFNode01(V value) {
        this.value = value;
    }
}

class UnionFind01<V> {
    private Map<V, UFNode01<V>> nodeMaps = new HashMap<>();
    private Map<UFNode01<V>, UFNode01<V>> parentMaps = new HashMap<>();
    private Map<UFNode01<V>, Integer> countMaps = new HashMap<>();

    UnionFind01(List<V> values) {
        for(V value: values) {
            UFNode01<V> node = new UFNode01<>(value);
            nodeMaps.put(value, node);
            parentMaps.put(node, node);
            countMaps.put(node,1);
        }
    }

    private UFNode01<V> findParent(UFNode01<V> node) {
        List<UFNode01<V>> nodes = new ArrayList<>();
        while (node != parentMaps.get(node)) {
            nodes.add(node);
            node = parentMaps.get(node);
        }

        for (UFNode01<V> nd : nodes) {
            // 设置父元素
            parentMaps.put(nd, node);
        }

        return node;
    }

    public boolean isSameSet(V v1, V v2) {
        if (!nodeMaps.containsKey(v1) || !nodeMaps.containsKey(v2)) {
            return false;
        }

        return findParent(nodeMaps.get(v1)) == findParent(nodeMaps.get(v2));
    }

    public void union(V v1, V v2) {

        if (!nodeMaps.containsKey(v1) || !nodeMaps.containsKey(v2)) {
            return;
        }

        UFNode01<V> parentV1 = findParent(nodeMaps.get(v1));
        UFNode01<V> parentV2 = findParent(nodeMaps.get(v2));
        if (parentV1 == parentV2) {
            return;
        }

        if (countMaps.get(parentV1) >= countMaps.get(parentV2)) {
            parentMaps.put(parentV2,parentV1);
            countMaps.put(parentV1,countMaps.get(parentV1) + countMaps.get(parentV2));
            countMaps.remove(parentV2);
        }else {
            parentMaps.put(parentV1, parentV2);
            countMaps.put(parentV2,countMaps.get(parentV1) + countMaps.get(parentV2));
            countMaps.remove(parentV1);
        }
    }
}



public class _并查集01 {
    public static void main(String[] args) {

    }
}
